package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC992 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 不是因为复杂，而是因为经典
     * 未来需要再次复习此道题目
     * 官方思路真是犀利，使用双指针解决的问题的问法基本都会出现「最小」、「最大」这样的字眼。
     * 问题转化，hard的常见难点
     * @return:
     */
    public class Solution {

        public int subarraysWithKDistinct(int[] A, int K) {
            return atMostKDistinct(A, K) - atMostKDistinct(A, K - 1);
        }

        /**
         * @param A
         * @param K
         * @return 最多包含 K 个不同整数的子区间的个数
         */
        private int atMostKDistinct(int[] A, int K) {
            int len = A.length;
            int[] freq = new int[len + 1];

            int left = 0;
            int right = 0;
            // [left, right) 里不同整数的个数
            int count = 0;
            int res = 0;
            // [left, right) 包含不同整数的个数小于等于 K
            while (right < len) {
                if (freq[A[right]] == 0) {
                    count++;
                }
                freq[A[right]]++;
                right++;

                while (count > K) {
                    freq[A[left]]--;
                    if (freq[A[left]] == 0) {
                        count--;
                    }
                    left++;
                }
                // [left, right) 区间的长度就是对结果的贡献
                res += right - left;
            }
            return res;
        }
    }


    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC992 an = new LC992();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
